package com.demo.example.hot100;

public class NextPermutation {
    //也可以考虑暴力？先生成全部数组后排序进行，自己后面看看吧
    public static void nextPermutation(int[] nums){
        if(nums==null || nums.length<2){
            return;
        }
        int i=nums.length-2;
        while(i>=0 && nums[i]>=nums[i+1]){
            i--;
        }
        if(i>=0){
            int j= nums.length-1;
            while(j>=0 && nums[i]>=nums[j]){
                j--;
            }
            swap(nums,i,j);
        }
        reverse(nums,i+1);
    }
    public static void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    public static void reverse(int[] nums,int start){
        int left=start,right= nums.length-1;
        while(left<right){
            swap(nums,left,right);
            left++;
            right--;
        }
    }
}
